using System;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;
using Unity.Mathematics;
using static Unity.Collections.AllocatorManager;
using UnityEngine;
using System.Linq;

namespace AnimCollections {
#if UNITY_EDITOR
    [System.Diagnostics.DebuggerTypeProxy(typeof(SparsePtrListDebugView<>))]
#endif
    public unsafe struct SparsePtrList<T> : IDisposable where T : unmanaged {

        // 在申请的内存中， dataPtr[capacity] 后接着存 freeIndexPtr[capacity]
        T** dataPtr;
        int* freeIndexPtr;
        int capacity;
        int dataCount;
        int freeCount;
        AllocatorHandle allocator;

        public int Count => dataCount - freeCount;
        public int MaxCount => dataCount;

        public SparsePtrList(int capacity, AllocatorHandle allocator) {
            dataPtr = null;
            freeIndexPtr = null;
            dataCount = 0;
            freeCount = 0;
            this.capacity = 0;
            this.allocator = allocator;
            Resize(math.max(4, capacity));
        }

        public void Dispose() {
            if (dataPtr == null) return;
            Clear();
            var alignOf = UnsafeUtility.AlignOf<IntPtr>();
            var sizeOfT = sizeof(T*);
            var sizeOfIndex = sizeof(int);
            var size = (sizeOfT + sizeOfIndex);
            allocator.Free((void*)dataPtr, size, alignOf, capacity);
            dataPtr = null;
        }

        public void Clear() {
            dataCount = 0;
            freeCount = 0;
        }

        public T* this[int index] {
            get {
#if ENABLE_UNITY_COLLECTIONS_CHECKS
                if (index < 0 || index >= dataCount) throw new ArgumentOutOfRangeException($"index of SparsePtrList out of range. {index} / ({dataCount} - {freeCount})");
#endif
                return dataPtr[index];
            }
            set {
#if ENABLE_UNITY_COLLECTIONS_CHECKS
                if (index < 0 || index >= dataCount) throw new ArgumentOutOfRangeException($"index of SparsePtrList out of range. {index} / ({dataCount} - {freeCount})");
#endif
                dataPtr[index] = value;
            }
        }

        public int Add(T* item) {
            if (freeCount > 0) {
                // 插入在空白处
                int index = freeIndexPtr[--freeCount];
                dataPtr[index] = item;
                return index;
            } else {
                // 放在最后
                if (dataCount == capacity) {
                    Resize(capacity * 2);
                }
                int index = dataCount++;
                dataPtr[index] = item;
                return index;
            }
        }

        public void RemoveAt(int index) {
#if ENABLE_UNITY_COLLECTIONS_CHECKS
            // index 不能被重复移除，但是这个检查很耗，所以不在发布版本做
            if (GetFreeIndexArray().Contains(index)) {
                throw new IndexOutOfRangeException($"index({index}) has been removed");
            }
#endif
            dataPtr[index] = default;
            freeIndexPtr[freeCount++] = index;
        }

        void Resize(int newCapacity) {
#if ENABLE_UNITY_COLLECTIONS_CHECKS
            Debug.Assert(newCapacity > 0);
            Debug.Assert(newCapacity > capacity);
#endif
            ResizeExact(ref allocator, newCapacity + (newCapacity & 1)); // capacity保证为偶数
        }

        void ResizeExact(ref AllocatorHandle allocator, int newCapacity) {
#if ENABLE_UNITY_COLLECTIONS_CHECKS
            Debug.Assert(freeCount == 0); // 肯定是满了才扩容的，所以freeIndex应该是空的,不需要copy
            Debug.Assert(newCapacity % 2 == 0); // 要求是偶数
#endif

            CollectionHelper.CheckAllocator(this.allocator);
            void* newPointer = null;

            // 需要尺寸 (sizeOfT + sizeOfInt) * n
            // 前面放 n*T(数据正文) 后面放 n*int(freeIndex数组)
            var alignOf = UnsafeUtility.AlignOf<IntPtr>();
            var sizeOfT = sizeof(T*);
            var sizeOfInt = sizeof(int);
            var size = (sizeOfT + sizeOfInt);

            // if (newCapacity > 0) {
            //     newPointer = allocator.Allocate(size, alignOf, newCapacity);
            //
            //     // if (dataPtr != null && capacity > 0) {
            //     //     var itemsToCopy = math.min(newCapacity, capacity);
            //     //     var bytesToCopy = itemsToCopy * sizeOfT;
            //     //     // UnsafeUtility.MemCpy(newPointer, dataPtr, bytesToCopy);
            //     // }
            // }
            newPointer = allocator.Allocate(size, alignOf, newCapacity);

            var newDataPtr = (T**)newPointer;
            var newFreeIndexPtr = (int*)((byte*)newPointer + newCapacity * sizeOfT);

            // copy data
            if (dataPtr != null && dataCount > 0) {
                var bytesOfT = capacity * sizeOfT;
                var bytesOfInt = capacity * sizeOfT;
                UnsafeUtility.MemCpy(newDataPtr, dataPtr, bytesOfT);
                UnsafeUtility.MemCpy(newFreeIndexPtr, freeIndexPtr, bytesOfInt);
                allocator.Free((void*)dataPtr, size, alignOf, capacity);
            }

            freeIndexPtr = newFreeIndexPtr;
            capacity = newCapacity;
            // dataCount = dataCount; 不变
            dataPtr = newDataPtr;

        }

#if UNITY_EDITOR
        public T[] GetDataArray() {
            T[] array = new T[dataCount];
            for (int i = 0; i < dataCount; i++) {
                if (dataPtr[i] == null) array[i] = default;
                else array[i] = *dataPtr[i];
            }
            return array;
        }

        public IntPtr[] GetDataPtrArray() {
            var array = new IntPtr[dataCount];
            for (int i = 0; i < dataCount; i++) {
                array[i] = new(dataPtr[i]);
            }
            return array;
        }

        public int[] GetFreeIndexArray() {
            int[] array = new int[freeCount];
            for (int i = 0; i < freeCount; i++) {
                array[i] = freeIndexPtr[i];
            }
            return array;
        }

        public IntPtr[] GetFreeIndexPtrArray() {
            var array = new IntPtr[freeCount];
            for (int i = 0; i < freeCount; i++) {
                array[i] = new(freeIndexPtr[i]);
            }
            return array;
        }
    }


    internal class SparsePtrListDebugView<T> where T : unmanaged {
        private SparsePtrList<T> list;

        public int Count => list.Count;
        public T[] Data => list.GetDataArray();
        public IntPtr[] DataPtr => list.GetDataPtrArray();
        public int[] FreeIndices => list.GetFreeIndexArray();
        public IntPtr[] FreeIndicesPtr => list.GetFreeIndexPtrArray();

        public SparsePtrListDebugView(SparsePtrList<T> list) {
            this.list = list;
        }
#endif
    }
}